#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 114. 二叉树展开为链表.py
@time: 2022/2/27 19:26
@desc: https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
给你二叉树的根结点 root ，请你将它展开为一个单链表：
    - 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
    - 展开后的单链表应该与二叉树 先序遍历 顺序相同。

>
@解题思路：
    1. 递归
    2. 记住flatten的作用只有一个，就是把一棵树拉成目标的形状
    3. Ot(N), Os(N)
'''
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        if not root: return
        # 拉平左子树
        self.flatten(root.left)
        # 保存原右子树后，将拉平的左子树接到根节点的右子树
        right = root.right
        root.right = root.left
        root.left = None
        # 遍历到新右子树的尾部
        while root.right:
            root = root.right
        # 拉平原右子树
        self.flatten(right)
        # 接到新右子树的尾部
        root.right = right